#include <stdio.h>
#include <stdlib.h>
void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}
void shift_down(int a[], int n, int i)
{

    int temp = a[i];
    while (2 * i + 1 < n)
    {
        int t = 2 * i + 1;
        if (t + 1 < n && a[t] < a[t + 1])
            t++;
        if (temp < a[t])
        {
            a[i] = a[t];
            i = t;
        }
        else
            break;
    }
    a[i] = temp;
}
void shift_up(int a[], int n, int i)
{
    int temp = a[i];
    for (; i < n && i > 0 && a[(i - 1) / 2] < temp; i = (i - 1) / 2)
        a[i] = a[(i - 1) / 2];
    a[i] = temp;
}
void build_heap_up(int a[], int n)
{
    for (int i = 0; i < n; i++)
        shift_up(a, n, i);
}
void build_heap(int a[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        shift_down(a, n, i);
}

void heap_sort(int a[], int n)
{
    // 1.build_heap
    build_heap_up(a, n);
    printf("heap:\n");
    for (int i = 0; i < 10; i++)
        printf("%3d", a[i]);
    printf("\n");
    // heap:
    //  30 26 13 14 17  4  7  3 10  8
    //  30 26 13  8 17 10  7  4  3 14
    // 2.heap_sort
    int len = n;
    for (int i = n - 1; i > 0; i--)
    {
        swap(a[0], a[i]);
        shift_down(a, --len, 0);
    }
}

int main()
{
    /*******************code*******************/
    int a[] = {4, 3, 10, 8, 14, 13, 7, 30, 26, 17};
    heap_sort(a, 10);
    printf("heap_sort\n");
    for (int i = 0; i < 10; i++)
        printf("%3d", a[i]);
    printf("\n");
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
